import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-09-01
 * Time: 16:16
 */
public class Test {
    public static void main1(String[] args) {
        MySingleList list = new MySingleList();
        list.createList();
        list.display();
        MySingleList.ListNode ret = list.middleNode();
        System.out.println(ret.val);
        MySingleList.ListNode ret1 = list.reverseList();
        list.display2(ret1);
        int ret2 = list.kthToLast(5);
        System.out.println(ret2);
//        System.out.println(list.size());
//        list.addFirst(999);
//        list.addFirst(222);
//        list.addFirst(888);
//        list.display();
//        list.addLast(888);
//        list.addLast(222);
//        list.display();
//        list.remove(999);
//        list.display();
//        list.removeAllKey(222);
//        list.display();
//        list.clear();
//        list.display();
    }

    //合并两个有序链表
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                               MySingleList.ListNode headB) {
        MySingleList.ListNode newH = new MySingleList.ListNode(-1);
        MySingleList.ListNode cur = newH;
        while(headA != null && headB != null){
            if(headA.val < headB.val) {
                cur.next = headA;
                headA = headA.next;
            }else {
                cur.next = headB;
                headB = headB.next;
            }
            cur = cur.next;
        }
        if(headA != null) {
            cur.next = headA;
        }else {
            cur.next = headB;
        }
        return newH.next;
    }

    public static void main2(String[] args) {
        MySingleList list1 = new MySingleList();
        list1.addLast(11);
        list1.addLast(21);
        list1.addLast(31);
        list1.addLast(41);
        list1.addLast(51);
        MySingleList list2 = new MySingleList();
        list2.addLast(12);
        list2.addLast(23);
        list2.addLast(34);
        list2.addLast(45);
        list2.addLast(56);
        MySingleList.ListNode newH = mergeTwoLists(list1.head, list2.head);
        list1.display2(newH);
    }

    public static void main3(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(56);
        list.addLast(23);
        list.addLast(45);
        list.addLast(12);
        list.addLast(34);
        list.display();
        MySingleList.ListNode newH = list.partition(40);
        list.display2(newH);

        MySingleList list1 = new MySingleList();
        list1.addLast(23);
        list1.addLast(21);
//        list1.addLast(34);
        list1.addLast(21);
        list1.addLast(23);
        System.out.println(list1.chkPalindrome());
    }


    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        int len1 = 0;
        int len2 = 0;
        //1.求出两条链表的长度
        while(pl != null ) {
            len1++;
            pl = pl.next;
        }
        while(ps != null){
            len2++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //2.求差值
        int len = len1 - len2;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = len2 - len1;
        }
        //走完上述两步，pl一定指向最长的链表，ps一定指向最短的链表
        //4.先让最长的链表走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        //这种情况ps和pl都为null 没相交
        if(pl == null) {
            return null;
        }
        return ps;
    }
    //创建Y型双链
    public static void createCut(MySingleList.ListNode headA, MySingleList.ListNode headB){
        headB.next.next = headA.next;
    }
    public static void main4(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(56);
        list.addLast(23);
        list.addLast(45);
        list.addLast(12);
        list.addLast(34);
        MySingleList list2 = new MySingleList();
        list2.addLast(12);
        list2.addLast(23);
        list2.addLast(34);
        list2.addLast(45);
        list2.addLast(56);
        list2.addLast(67);
        createCut(list.head,list2.head);
        MySingleList.ListNode ret = getIntersectionNode(list.head,list2.head);
        System.out.println(ret.val);
        list.display2(list.head);
        list2.display2(list2.head);
    }

    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(56);
        list.addLast(23);
        list.addLast(45);
        list.addLast(12);
        list.addLast(34);
        list.createLoop();
        System.out.println(list.hasCycle());
        MySingleList.ListNode ret = list.detectCycle(list.head);
        System.out.println(ret.val);
    }
}


